package com.mgq.algorithm.link;

import java.util.Stack;

/**
 * @author MaGuangQi
 * 判断一个链表是否为回文结构 234题
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * 1->2->2->1 true
 * 1->2 false
 * @date 2021-12-29 14:49
 **/
public class PalindromeLinkedList_234 {
    public boolean isPalindrome(ListNode head) {
        //思路一,用栈解决
        //全部压栈 妮妮和冯绍峰问题  回文串其实就是正过来和返过来都一样
        //利用栈,我们把元素全部入栈,出栈呢正好相反,依次比较就知道一样不一样了
        if (head == null || head.next == null) {
            return false;
        }
        ListNode tHead = head;
        Stack<ListNode> stacks = new Stack<>();
        while (head != null) {
            stacks.push(head);
            head = head.next;
        }
        while (tHead != null) {
            if (tHead.val != stacks.pop().val) {
                return false;
            }
            tHead = tHead.next;
        }
        return true;
    }

    public boolean isPalindrome2(ListNode head) {
        //思路一,用栈解决
        //全部压栈 妮妮和冯绍峰问题  回文串其实就是正过来和返过来都一样
        //利用栈,只压右半部分.这样空间复杂度就是O(N/2)
        //使用快慢指针. 找到中间节点
        if (head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;
        while (slow != null && fast != null) {
            slow=slow.next;
            fast = fast.next.next;
        }
        //中间位置
        ListNode mid=slow;
        Stack<ListNode> stacks = new Stack<>();
       return false;
    }
}
